package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/repeated-string-match/description/
 * @create 2025/9/27 16:32
 * @since JDK17
 */

public class Solution83 {
    char[] s1, s2, s3;
    int BASE = 599;
    long get(long[]p, long[]h, int l, int r) {
        long ans = h[r];
        ans -= l == 0 ? 0 : (h[l - 1] * p[r - l + 1]);
        return ans;
    }

    public int repeatedStringMatch(String a, String b) {
        s1 = a.toCharArray();
        s2 = b.toCharArray();
        int n = s1.length, m = s2.length, k = (m + n - 1) / n, len = 0;
        s3 = new char[(k + 1) * n];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                s3[len++] = s1[j];
            }
        }
        long[] p = new long[len], h = new long[len];
        p[0] = 1;
        h[0] = s3[0];
        for (int i = 1; i < len; i++) {
            p[i] = p[i - 1] * BASE;
            h[i] = h[i - 1] * BASE + s3[i];
        }
        long hash = 0;
        for (int i = 0; i < m; i++) {
            hash = hash * BASE + s2[i];
        }

        for (int l = 0, r = m - 1; r < len; r++, l++) {
            if (get(p, h, l, r) == hash) {
                return r < n * k ? k : k + 1;
            }
        }

        return -1;
    }
}
